package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution_47 {

    private boolean[] visited;
    private Map<Integer, Integer> map = new HashMap<>();

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        visited = new boolean[nums.length];
        dps(nums, new ArrayList<>());
        return res;
    }

    private void dps(int[] nums, List<Integer> list) {
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                Integer preValue = map.getOrDefault(list.size(), null);
                if (preValue == null || preValue != nums[i]) {
                    list.add(nums[i]);
                    map.put(list.size() - 1, nums[i]);
                    visited[i] = true;
                    dps(nums, list);
                    visited[i] = false;
                    map.remove(list.size());
                    list.remove(list.size() - 1);
                }
            }
        }
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
        }
    }

    public static void main(String[] args) {
        Solution_47 model = new Solution_47();
//        List<List<Integer>> list = model.permuteUnique(new int[]{1, 1, 2});
//        List<List<Integer>> list = model.permuteUnique(new int[]{1, 2, 3});
        List<List<Integer>> list = model.permuteUnique(new int[]{-5, 9, 4, 2, -2, 9, 10, 4, 0});
        for (List<Integer> integers : list) {
            System.out.println(integers);
        }
        System.out.println(list.size());

        // 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
    }
}
